home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d14 / atre12.arc / ATREEDLL.ARC / ATREE.C next >
C/C++ Source or Header  |  1991-07-27  |  71KB  |  2,096 lines
  1. /*****************************************************************************
  2.  ****                                                                     ****
  3.  **** atree.c                                                             ****
  4.  ****                                                                     ****
  5.  **** Copyright (C) A. Dwelly and W.W. Armstrong, 1990.                   ****
  6.  ****                                                                     ****
  7.  **** All rights reserved.                                                ****
  8.  ****                                                                     ****
  9.  **** This is the program file for the "research" version of the adaptive ****
  10.  **** logic network package based on work done by Prof. W. W. Armstrong   ****
  11.  **** and others in the Department of Computing Science, University of    ****
  12.  **** Alberta, and previous work at the Universite de Montreal, and at    ****
  13.  **** AT&T Bell Laboratories, Holmdel, N. J.  The software demonstrates   ****
  14.  **** that networks consisting of many layers of linear threshold         ****
  15.  **** elements can indeed be effectively trained.                         ****
  16.  ****                                                                     ****
  17.  **** License:                                                            ****
  18.  **** A royalty-free license is granted for the use of this software for  ****
  19.  **** NON-COMMERCIAL PURPOSES ONLY. The software may be copied and        ****
  20.  **** modified provided this notice appears in its entirety and unchanged ****
  21.  **** in all copies, whether changed or not.  Persons modifying the code  ****
  22.  **** are requested to state the date, the changes made and who made them ****
  23.  **** in the modification history.                                        ****
  24.  ****                                                                     ****
  25.  **** Warranty:                                                           ****
  26.  **** No warranty of any kind is provided with this software.             ****
  27.  **** This software is not supported.  Neither the authors, nor the       ****
  28.  **** University of Alberta, its officers, agents, servants or employees  ****
  29.  **** shall be liable or responsible in any way for any damage to         ****
  30.  **** property or direct personal or consequential injury of any nature   ****
  31.  **** whatsoever that may be suffered or sustained by any licensee, user  ****
  32.  **** or any other party as a consequence of the use or disposition of    ****
  33.  **** this software.                                                      ****
  34.  ****                                                                     ****
  35.  **** Patent:                                                             ****
  36.  **** The use of a digital circuit which transmits a signal indicating    ****
  37.  **** heuristic responsibility is protected by U. S. Patent 3,934,231     ****
  38.  **** and others assigned to Dendronic Decisions Limited of Edmonton,     ****
  39.  **** W. W. Armstrong, President.                                         ****
  40.  ****                                                                     **** 
  41.  **** A royalty-free license is granted for the use of this patent to     ****
  42.  **** run this software for NON-COMMERCIAL PURPOSES ONLY and the          ****
  43.  **** extension of this patent license to modified versions of this       ****
  44.  **** software is granted provided the purpose is NON-COMMERCIAL ONLY.    ****
  45.  ****                                                                     ****
  46.  **** Modification history:                                               ****
  47.  ****                                                                     ****
  48.  **** 90.09.05 Initial implementation, A.Dwelly                           ****
  49.  **** 91.04.15 Port to PC and minor bug fixes, R. Manderscheid            ****
  50.  **** 91.05.31 Port to Windows & Windows Extensions, M. Thomas            ****
  51.  ****                                                                     ****
  52.  *****************************************************************************/
  53.  
  54. #pragma inline
  55.  
  56. /*****************************************************************************
  57.  ****                                                                     ****
  58.  **** Include Files                                                       ****
  59.  ****                                                                     ****
  60.  *****************************************************************************/
  61.  
  62. #include <stdio.h>
  63. #include <stdlib.h>
  64. #include <windows.h>
  65. #include "atree.h"
  66.  
  67. #define assert(exp)\
  68.     {\
  69.     if (!(exp))\
  70.         {\
  71.         char szBuffer[30]; \
  72.         wsprintf(szBuffer, "%s, Line %d",\
  73.             __FILE__, __LINE__);\
  74.         MessageBox (NULL, szBuffer, "Assertion Failed",\
  75.                 MB_OK | MB_ICONSTOP);\
  76.         }\
  77.     }
  78.  
  79. /*****************************************************************************
  80.  ****                                                                     ****
  81.  **** Constants                                                           ****
  82.  ****                                                                     ****
  83.  *****************************************************************************/
  84.  
  85. #define AND 0
  86. #define RIGHT 1
  87. #define LEFT 2
  88. #define OR 3
  89.  
  90. #define TRUE 1              /* As usual */
  91. #define FALSE 0
  92. #define UNEVALUATED 2       /* We complete the lattice of boolean functions */
  93. #define ATREE_ERROR -1      /* Don't want conflict with Windows.h ERROR */
  94. #define BOTTOM UNEVALUATED  /* Synonyms */
  95. #define TOP ATREE_ERROR
  96. #define LEFTLEAF 0xF0       /* masks for leaf_flag and cmp_flag */
  97. #define RIGHTLEAF 0x0F
  98.  
  99. #define MAX_RETRY 50        /* No. of retrys before an error in atree_rand_walk */
  100.  
  101. /* Initialisation values */
  102.  
  103. #define MAXSET 63
  104. #define ABOVEMID 32
  105. #define BELOWMID 31
  106. #define MINSET 0
  107.  
  108. /* memory manager constants */
  109.  
  110. #define SEGLENGTH 65536L    /* 64K */
  111. #define NUMSEGS 64         /* can manage up to 4096K */
  112.  
  113. /*
  114.  * Tricky Macros
  115.  */
  116.  
  117. #define Printf(str,fmt) {\
  118.                         char string[] = str; \
  119.                         wsprintf(szBuffer,string,fmt);\
  120.                         }
  121.  
  122. /* Public and private procedures */
  123.  
  124. #define public
  125. #define private static
  126.  
  127. /* Infinite loops - for EVER */
  128.  
  129. #define EVER (;;)
  130.  
  131. /* Printing out the boolean lattice */
  132.  
  133. #define PRINTBOOL(b) if (b == TRUE) {Printf("1",0);} else if (b == FALSE)\
  134.     {Printf("0",0);} else if (b == UNEVALUATED) {Printf("U",0);} else \
  135.     if (b == ATREE_ERROR) {Printf("E",0);} else {Printf("?",0);}
  136.  
  137. /* Verbosity */
  138.  
  139. #define VERBOSE(level,s) if (verbosity >= level) {s ;}
  140.  
  141. /* Byte size in bits.*/
  142.  
  143. #define BYTE (sizeof(char)*8)
  144.  
  145. /* Tree evaluation macros */
  146.  
  147. #define EVAL(slf,side) ( (slf & (tree -> leaf_flag)) ? \
  148.                             ( (slf & (tree -> cmp_flag)) ? \
  149.                                    !bv_extract(tree -> side.leaf,vec): \
  150.                                    bv_extract(tree -> side.leaf,vec) ) : \
  151.                             atree_eval(tree -> side.child,vec) )
  152.  
  153. #define LEFTEVAL (tree -> sig_left = EVAL(LEFTLEAF,left))
  154.  
  155. #define RIGHTEVAL (tree -> sig_right = EVAL(RIGHTLEAF,right))
  156.  
  157. /*
  158.  * Types
  159.  */
  160.  
  161. typedef int bool;        /*
  162.                           * Only TRUE, FALSE, UNEVALUATED or ATREE_ERROR
  163.                           * are used in these variables
  164.                           */
  165.  
  166. /*
  167.  * some static variables needed by the atree memory manager
  168.  */
  169.  
  170. /* HANDLE to each segment */
  171. static HANDLE seg[NUMSEGS];
  172.  
  173. /* memory free in each segment */
  174. static WORD freemem[NUMSEGS];
  175.  
  176. /*
  177.  * Preliminary Private Procedure Declarations
  178.  */
  179.  
  180. private void NEAR PASCAL         WinMem_Init();
  181. private LPATREE NEAR PASCAL      build_tree(LPINT, char far *,int,int,LPATREE);
  182. private void NEAR PASCAL         print_tree(LPATREE, int, int, int);
  183. private bool NEAR PASCAL         train(LPATREE, LPBIT_VEC, bool);
  184. private void NEAR PASCAL         adapt(LPATREE, LPBIT_VEC, bool);
  185. private char NEAR PASCAL         node_function(LPATREE);
  186.  
  187.  
  188. /*
  189.  * LibMain Procedure to initialize DLL
  190.  */
  191.  
  192. #pragma argsused
  193.  
  194. long FAR PASCAL VerbosityWndProc(HWND, WORD, WORD, LONG);
  195.  
  196. HANDLE hInst;
  197. char szVerbLine1[60];
  198. char szVerbLine2[60];
  199. short cyChar;
  200.  
  201. int FAR PASCAL LibMain (HANDLE hInstance, WORD wDataSeg, WORD wHeapSize, LPSTR lpszCmdLine)
  202.  
  203.     {
  204.     
  205.     WNDCLASS wndclass;
  206.     
  207.     hInst = hInstance;
  208.     
  209.     wndclass.style          = CS_NOCLOSE;
  210.     wndclass.lpfnWndProc    = VerbosityWndProc;
  211.     wndclass.cbClsExtra     = 0;
  212.     wndclass.cbWndExtra     = 0;
  213.     wndclass.hInstance      = hInstance;
  214.     wndclass.hIcon          = LoadIcon(hInstance, "atreeico");
  215.     wndclass.hCursor        = LoadCursor(NULL, IDC_ARROW);
  216.     wndclass.hbrBackground  = GetStockObject(WHITE_BRUSH);
  217.     wndclass.lpszMenuName   = NULL;
  218.     wndclass.lpszClassName  = "VERBOSITY";
  219.         
  220.     RegisterClass(&wndclass);
  221.     
  222.     if (wHeapSize > 0)
  223.         UnlockData(0);
  224.         
  225.     return 1;
  226.     
  227.     }
  228.     
  229. long FAR PASCAL VerbosityWndProc(HWND hwnd, WORD message, WORD wParam, LONG lParam)
  230.     {
  231.     static short cxChar, cxCaps;
  232.     char szBuffer[10];
  233.     HDC hdc;
  234.     short i;
  235.     PAINTSTRUCT ps;
  236.     TEXTMETRIC tm;
  237.     
  238.     switch (message)
  239.         {
  240.         case WM_CREATE:
  241.             hdc = GetDC(hwnd);
  242.             
  243.             GetTextMetrics(hdc, &tm);
  244.             cxChar = tm.tmAveCharWidth;
  245.             cxCaps = (tm.tmPitchAndFamily & 1 ? 3 : 2) * cxChar / 2 ;
  246.             cyChar = tm.tmHeight + tm.tmExternalLeading ;
  247.             
  248.             ReleaseDC(hwnd,hdc);
  249.             return 0;
  250.             
  251.         case WM_PAINT:
  252.  
  253.             hdc = BeginPaint(hwnd, &ps);
  254.           
  255.             TextOut (hdc, 5 * cxChar, cyChar * 6, szVerbLine1, lstrlen(szVerbLine1));            
  256.             TextOut (hdc, 5 * cxChar, cyChar * 7, szVerbLine2, lstrlen(szVerbLine2));
  257.             
  258.             EndPaint(hwnd, &ps);
  259.             
  260.             return 0;
  261.             
  262.         case WM_DESTROY:
  263. /*            PostQuitMessage(0);*/
  264.             return 0;
  265.         }
  266.         
  267.     return DefWindowProc(hwnd,message, wParam, lParam);
  268.     }
  269.                         
  270. /*****************************************************************************
  271.  *****************************************************************************
  272.  ****                                                                     ****
  273.  ****                        Public Routines                              ****
  274.  ****                                                                     ****
  275.  *****************************************************************************
  276.  *****************************************************************************/
  277.  
  278.  
  279. /*****************************************************************************
  280.  ****                                                                     ****
  281.  **** void FAR PASCAL atree_init()                                        ****
  282.  ****                                                                     ****
  283.  **** Synopsis:                                                           ****
  284.  ****                                                                     ****
  285.  **** Initialises various global variables, and makes an initial call to  ****
  286.  **** the random number seed routine.  Checks to make sure Windows is in  ****
  287.  **** protect mode.                                                       ****
  288.  ****                                                                     ****
  289.  *****************************************************************************/
  290.  
  291. public void FAR PASCAL
  292. atree_init()
  293. {
  294.     DWORD   c;
  295.  
  296.     c = GetTickCount();
  297.     (void) srand((int) c);
  298.  
  299.     c = GetWinFlags();
  300.     if (!(c & WF_PMODE))
  301.         {
  302.         MessageBox(NULL, "Atree software cannot run\nin Windows Real Mode!",
  303.                    "Not in Protected Mode!", MB_OK | MB_ICONSTOP);
  304.         exit(0);
  305.         }
  306. }
  307.  
  308. /*****************************************************************************
  309.  ****                                                                     ****
  310.  **** LPBIT_VEC atree_rand_walk(num,width,p)                              ****
  311.  ****                                                                     ****
  312.  **** int num;                                                            ****
  313.  **** int width;                                                          ****
  314.  **** int p;                                                              ****
  315.  ****                                                                     ****
  316.  **** Synopsis:                                                           ****
  317.  ****                                                                     ****
  318.  **** Creates an array of _num_ binary vectors, of _width_ bits where     ****
  319.  **** each is _p_ bits away from its neighbours in Hamming space. Each    ****
  320.  **** vector is unique.                                                   ****
  321.  **** This routine returns NULL if it's unable to find enough vectors.    ****
  322.  *****************************************************************************/
  323.  
  324. #pragma warn -pia
  325.  
  326. public LPBIT_VEC FAR PASCAL
  327. atree_rand_walk(num,width,p)
  328.  
  329. int num;
  330. int width;
  331. int p;
  332.  
  333. {
  334.     /*
  335.      * An initial vector is produced with random bits, and each subsequent
  336.      * vector in the random walk just has _p_ bits flipped. In order to
  337.      * guarantee that each vector is unique, it is checked against
  338.      * a chained list of vectors of the same bit sum. If it is not already
  339.      * in the chain it is appended to the end, or else the vector is discarded
  340.      * and the process repeats itself.
  341.      */
  342.  
  343.     LPBIT_VEC   bv_set;            /* An array of bit vectors */
  344.     LPBIT_VEC   pckd_vec;          /* The packed unique ? vector */
  345.     bool        unique;            /* Uniqueness flag set during testing */
  346.     LPINT       bit_sum_chain;     /* Pointers to vectors of equivalent bit sums */
  347.     LPINT       next_vec;          /* Chain array */
  348.     LPSTR       unpckd_vec;        /* An unpacked vector */
  349.     LPSTR       this_vec;          /* An unpacked vector */
  350.     LPSTR       mark_vec;          /* TRUE where a bit has been flipped */
  351.     int         i;
  352.     int         j;
  353.     int         old_bit_sum;       /* Last number of TRUE bits in vector */
  354.     int         bit_sum;           /* Current number of TRUE bits in vector */
  355.     int         retrys;            /* Number of attempts to find a unique vec */
  356.     int         victim;            /* The bit just twiddled */
  357.     int         current_vec;       /* Part of the chain */
  358.  
  359.     assert(num > 0);
  360.     assert(width > 0);
  361.     assert(p != 0);
  362.     assert(p <= width);
  363.  
  364.     /* Assign space in memory */
  365.  
  366.     bv_set = (LPBIT_VEC) WinMem_Malloc(LMEM_MOVEABLE | LMEM_ZEROINIT, (unsigned) num * sizeof(bit_vec));
  367.     MEMCHECK(bv_set);
  368.  
  369.     bit_sum_chain = (LPINT) WinMem_Malloc(LMEM_MOVEABLE | LMEM_ZEROINIT, (unsigned) (width+1) * sizeof(int));
  370.     MEMCHECK(bit_sum_chain);
  371.  
  372.     next_vec = (LPINT) WinMem_Malloc(LMEM_MOVEABLE | LMEM_ZEROINIT, (unsigned) num * sizeof(int));
  373.     MEMCHECK(next_vec);
  374.  
  375.     unpckd_vec = (LPSTR) WinMem_Malloc(LMEM_MOVEABLE | LMEM_ZEROINIT, (unsigned) width * sizeof(char));
  376.     MEMCHECK(unpckd_vec);
  377.  
  378.     this_vec = (LPSTR) WinMem_Malloc(LMEM_MOVEABLE | LMEM_ZEROINIT, (unsigned) width * sizeof(char));
  379.     MEMCHECK(this_vec);
  380.  
  381.     mark_vec = (LPSTR) WinMem_Malloc(LMEM_MOVEABLE | LMEM_ZEROINIT, (unsigned) width * sizeof(char));
  382.     MEMCHECK(mark_vec);
  383.  
  384.     /* Clear bit_sum_chain */
  385.  
  386.     for (i = 0; i <= width; i++)
  387.     {
  388.         bit_sum_chain[i] = -1;
  389.     }
  390.  
  391.     /* Clear next_vec */
  392.  
  393.     for (i = 0; i < num; i++)
  394.     {
  395.         next_vec[i] = -1;
  396.     }
  397.  
  398.     /* Create initial vector and bit sum */
  399.  
  400.     old_bit_sum = 0;
  401.     for (i = 0; i < width; i++)
  402.     {
  403.         if (unpckd_vec[i] = RANDOM(2))
  404.         {
  405.            old_bit_sum++;
  406.         }
  407.     }
  408.  
  409.     bv_set[0] = *(bv_pack(unpckd_vec,width));
  410.     bit_sum_chain[old_bit_sum] = 0;
  411.  
  412.     /* Random walk */
  413.  
  414.     for (i = 1; i < num; i++)
  415.     {
  416.  
  417.         /* allow multitasking */
  418.         Windows_Interrupt(1000);
  419.  
  420.         retrys = 0;
  421.         unique = FALSE;
  422.         while ((!unique) && (retrys < MAX_RETRY))
  423.         {
  424.             retrys++;
  425.  
  426.             /* Make a new vector */
  427.  
  428.             bit_sum = old_bit_sum;
  429.             for (j = 0; j < width; j++)
  430.             {
  431.                 this_vec[j] = unpckd_vec[j];
  432.                 mark_vec[j] = FALSE;
  433.             }
  434.  
  435.             for (j = 0; j < p; j++)
  436.             {
  437.                 do
  438.                 {
  439.                     victim = RANDOM(width);
  440.                 }
  441.                 while (mark_vec[victim]);
  442.  
  443.                 mark_vec[victim] = TRUE;
  444.                 this_vec[victim] = !this_vec[victim];
  445.                 if (this_vec[victim] == FALSE)
  446.                 {
  447.                     bit_sum--;
  448.                 }
  449.                 else
  450.                 {
  451.                     bit_sum++;
  452.                 }
  453.             }
  454.  
  455.             pckd_vec = bv_pack(this_vec,width);
  456.  
  457.             /* Compare it with the existing ones of equal bit length */
  458.  
  459.             if (bit_sum_chain[bit_sum] == -1)
  460.             {
  461.                 /* There are no other vectors with this bit sum, so ... */
  462.  
  463.                 unique = TRUE;
  464.                 bv_set[i] = *pckd_vec;
  465.                 bit_sum_chain[bit_sum] = i;     
  466.                 next_vec[i] = -1;
  467.             }
  468.             else
  469.             {
  470.                 current_vec = bit_sum_chain[bit_sum];
  471.                 for EVER /* We break out of here inside the loop */ 
  472.                 { 
  473.                     if (bv_equal(&(bv_set[current_vec]),pckd_vec))
  474.                     {
  475.                         /* This vector already exists,  unique = FALSE; */
  476.                         break;
  477.                     }
  478.                     else
  479.                     {
  480.                         if (next_vec[current_vec] == -1)
  481.                         {
  482.                             unique = TRUE;
  483.                             bv_set[i] = *pckd_vec;
  484.                             next_vec[current_vec] = i;
  485.                             next_vec[i] = -1;
  486.                             break;
  487.                         }
  488.                         else
  489.                         {
  490.                             current_vec = next_vec[current_vec];
  491.                         }
  492.                     }
  493.                 } /* for EVER */
  494.             } /* if (bit_sum_chain...) */
  495.         } /* while ((!unique... ))*/
  496.  
  497.         /*
  498.          * If Unique is TRUE at this point, we have a unique
  499.          * vector stored, we have to set up old_bit sum and unpckd_vec
  500.          * for the next vector.
  501.          * If unique is FALSE, we have tried to create a unique vector
  502.          * MAX_RETRY times, and failed. We therefore signal an error.
  503.          */
  504.  
  505.         if (unique)
  506.         {
  507.             for (j = 0; j < width; j++)
  508.             {
  509.                 unpckd_vec[j] = this_vec[j];
  510.             }
  511.             old_bit_sum = bit_sum;
  512.         }
  513.         else
  514.         {
  515.             error("random walk failed");
  516.         }
  517.     } /* for */
  518.  
  519.  
  520.     /* Free space in memory */
  521.  
  522.     WinMem_Free((LPSTR)bit_sum_chain);
  523.     WinMem_Free((LPSTR)next_vec);
  524.     WinMem_Free((LPSTR)unpckd_vec);
  525.     WinMem_Free((LPSTR)this_vec);
  526.     WinMem_Free((LPSTR)mark_vec);
  527.  
  528.     /* Return final vector */
  529.  
  530.     return(bv_set);
  531. }
  532.  
  533. #pragma warn .pia
  534.  
  535. /*****************************************************************************
  536.  ****                                                                     ****
  537.  **** LPATREE atree_create(numvars,leaves)                                ****
  538.  ****                                                                     ****
  539.  **** int numvars;                                                        ****
  540.  **** int leaves;                                                         ****
  541.  ****                                                                     ****
  542.  **** Synopsis:                                                           ****
  543.  ****                                                                     ****
  544.  **** Creates an Armstrong tree with _leaves_ number of leaves connected  ****
  545.  **** to _numvars_  variables and their complements.  The number of       ****
  546.  **** leaves should probably be at least twice _numvars_.                 ****
  547.  **** The node functions and the connections are picked at random.        ****
  548.  ****                                                                     ****
  549.  *****************************************************************************/
  550.  
  551. public LPATREE FAR PASCAL
  552. atree_create(numvars,leaves)
  553.  
  554. int numvars;
  555. int leaves;
  556.  
  557. {
  558.     LPATREE     tree;
  559.     LPINT       connection;
  560.     char far    *complemented;
  561.     char        comp;
  562.     int         numvarscount;
  563.     int         a;
  564.     int         b;
  565.     int         tmpi;
  566.     char        tmpb;
  567.     int         i;
  568.  
  569.     assert(leaves > 2);
  570.     assert(numvars > 0);
  571.  
  572.     /* Assign the memory to hold first part of tree, place as low in memory as possible */
  573.  
  574.     if ((leaves - 1) >= (SEGLENGTH / sizeof(atree)))
  575.         tree = (LPATREE) GlobalWire(GlobalAlloc(GMEM_MOVEABLE,(DWORD)SEGLENGTH));
  576.  
  577.     else
  578.         tree = (LPATREE) GlobalWire(GlobalAlloc(GMEM_MOVEABLE,((DWORD)leaves - 1) * sizeof(atree)));
  579.  
  580.     MEMCHECK(tree);
  581.  
  582.     /*
  583.      * Create a list of bit inputs and shuffle, complemented inputs
  584.      * are marked with a TRUE in the complemented array.
  585.      */
  586.  
  587.     connection = (LPINT) WinMem_Malloc(LMEM_MOVEABLE | LMEM_ZEROINIT, (unsigned) sizeof(int) * leaves);
  588.     MEMCHECK(connection);
  589.     complemented = (char far *) WinMem_Malloc(LMEM_MOVEABLE | LMEM_ZEROINIT, (unsigned) sizeof(int) * leaves);
  590.     MEMCHECK(complemented);
  591.  
  592.     comp = 0x00;
  593.     for (i = 0; i < leaves; i++)
  594.     {
  595.         numvarscount = i % numvars;
  596.         if (numvarscount == 0)
  597.         {
  598.             comp = ~(comp);
  599.         }
  600.         connection[i] = numvarscount;
  601.         complemented[i] = comp;
  602.     }
  603.  
  604.     /* Shuffle */
  605.  
  606.     for (i = 0; i < leaves; i++)
  607.     {
  608.         a = RANDOM(leaves);
  609.         b = RANDOM(leaves);
  610.         tmpi = connection[a];
  611.         connection[a] = connection[b];
  612.         connection[b] = tmpi;
  613.         tmpb = complemented[a];
  614.         complemented[a] = complemented[b];
  615.         complemented[b] = tmpb;
  616.     }
  617.  
  618.     /* Build tree */
  619.  
  620.     (void) build_tree(connection,complemented,0,leaves - 1,tree);
  621.         /*
  622.  
  623.     /* Free memory */
  624.  
  625.     WinMem_Free((LPSTR)connection);
  626.     WinMem_Free((LPSTR)complemented);
  627.  
  628.     /* Return results */
  629.  
  630.     return(tree);
  631. }
  632.  
  633. /*****************************************************************************
  634.  ****                                                                     ****
  635.  **** BOOL atree_eval(tree,vec)                                           ****
  636.  ****                                                                     ****
  637.  **** LPATREE tree;                                                       ****
  638.  **** LPBIT_VEC vec;                                                      ****
  639.  ****                                                                     ****
  640.  **** Synopsis:                                                           ****
  641.  ****                                                                     ****
  642.  **** Applies the _tree_ to the bit vector _vec_ and returns the result,  ****
  643.  **** 1 for true, and 0 for false.                                        ****
  644.  *****************************************************************************/
  645.  
  646. #pragma warn -pia
  647.  
  648. public BOOL FAR PASCAL
  649. atree_eval(tree,vec)
  650.  
  651. LPATREE tree;
  652. LPBIT_VEC vec;
  653.  
  654. {
  655.     bool    result;
  656.  
  657.     /*
  658.      *  We recursively work our way down the tree.
  659.      *  Since the && and || operators in C are lazy,
  660.      *  we automatically get the parsimony (ugly word) that we
  661.      *  want.
  662.      */
  663.  
  664.    switch (tree -> function)
  665.     {
  666.         case AND:
  667.             tree -> sig_right = UNEVALUATED;
  668.             result = LEFTEVAL && RIGHTEVAL;
  669.             break;
  670.  
  671.         case RIGHT:
  672.             tree -> sig_left = UNEVALUATED;
  673.             result = RIGHTEVAL;
  674.             break;
  675.  
  676.         case LEFT:
  677.             tree -> sig_right = UNEVALUATED;
  678.             result = LEFTEVAL;
  679.             break;
  680.  
  681.         case OR:
  682.             tree -> sig_right = UNEVALUATED;
  683.             result = LEFTEVAL || RIGHTEVAL;
  684.             break;
  685.     }
  686.  
  687.     return(result);
  688. }
  689.  
  690. #pragma warn .pia
  691.  
  692. /*****************************************************************************
  693.  ****                                                                     ****
  694.  **** BOOL atree_train(tree,tset,correct_result,bit_col,tset_size,        ****
  695.  ****                  no_correct,epochs,verbosity)                       ****
  696.  ****                                                                     ****
  697.  **** LPATREE tree;                                                       ****
  698.  **** LPBIT_VEC tset;                                                     ****
  699.  **** LPBIT_VEC correct_result;                                           ****
  700.  **** int bit_col;                                                        ****
  701.  **** int tset_size;                                                      ****
  702.  **** int no_correct;                                                     ****
  703.  **** int epochs;                                                         ****
  704.  **** int verbosity;                                                      ****
  705.  ****                                                                     ****
  706.  **** Synopsis:                                                           ****
  707.  ****                                                                     ****
  708.  **** This routine is the heart of the library. It takes an atree _tree_  ****
  709.  **** to be trained, an array of input vectors _tset_, an array of        ****
  710.  **** vectors, _correct_result_ where each bit column holds a correct bit ****
  711.  **** result for each vector in _tset_. [Note: Only a single vector is    ****
  712.  **** actually required here, but doing it this way make life convenient  ****
  713.  **** for training collections of trees for real numbers] An integer      ****
  714.  **** _bit_col_ denoting the column to be trained on. Another integer     ****
  715.  **** _test_size gives the size of both the _tset_ and _correct_result_   ****
  716.  **** arrays.                                                             ****
  717.  ****                                                                     ****
  718.  **** The _tree_ is trained until the number of vectors presented in      ****
  719.  **** _tset_ equals _epoch_ epochs, or the last presentation of the number****
  720.  **** in an epoch had at least _no_correct_ presentations.                ****
  721.  **** The _verbosity_ is currently 0 or 1.                                ****
  722.  **** The routine returns TRUE if it stopped because it succeeded         ****
  723.  **** _no_correct_ times.                                                 ****
  724.  ****                                                                     ****
  725.  *****************************************************************************/
  726.  
  727. public BOOL FAR PASCAL
  728. atree_train(tree,tset,correct_result,bit_col,tset_size,no_correct,
  729.             epochs,verbosity)
  730.  
  731. LPATREE tree;
  732. LPBIT_VEC tset;
  733. LPBIT_VEC correct_result;
  734. int bit_col;
  735. int tset_size;
  736. int no_correct;
  737. int epochs;
  738. int verbosity;
  739.  
  740. {
  741.     bool        no_correct_flag = FALSE;
  742.     int         i;
  743.     int         j;
  744.     int         cor_this_epoch;
  745.     int         vec_num;
  746.     LPBIT_VEC   vec;
  747.     char        szBuff[60];
  748.     HWND        hwnd;
  749.  
  750.     /* For the specified number of epochs */
  751.  
  752.     VERBOSE(1,  hwnd = CreateWindow("VERBOSITY", "atree Training Progress",
  753.                                     WS_OVERLAPPEDWINDOW,
  754.                                     CW_USEDEFAULT, CW_USEDEFAULT,
  755.                                     250, 180,
  756.                                     NULL, NULL, hInst, NULL);
  757.                 lstrcpy(szVerbLine1,  "Beginning Training...");
  758.                 lstrcpy(szVerbLine2, " ");
  759.                 ShowWindow(hwnd, SW_SHOW);
  760.                 UpdateWindow(hwnd)
  761.            );
  762.  
  763.     for (i = 0; i < epochs; i++)
  764.     {
  765.         cor_this_epoch = 0;
  766.  
  767.         VERBOSE(1,wsprintf(szBuff,"Epoch : %d   ",i));
  768.  
  769.         /* For the elements of the test set */
  770.  
  771.         for (j = 0; j < tset_size; j++)
  772.         {
  773.             /* Pick a random vector */
  774.  
  775.             vec_num = RANDOM(tset_size);
  776.             vec = tset + vec_num;
  777.  
  778.             /* allow for multitasking */
  779.             Windows_Interrupt(1000);
  780.  
  781.             /* Train the tree */
  782.  
  783.             if (train(tree,vec,(bool)bv_extract(bit_col,correct_result + vec_num)))
  784.             {
  785.                 /* The tree succeeded */
  786.  
  787.                 cor_this_epoch++;
  788.                 if (cor_this_epoch == no_correct)
  789.                 {
  790.                     no_correct_flag = TRUE;
  791.                     break; /* out of this epoch */
  792.  
  793.                 } /* if (cor_this...) */
  794.             } /* if (train..) */
  795.         } /* for (j = ..) */
  796.  
  797.         VERBOSE(1,wsprintf(szVerbLine2,"Number correct was %d   ",cor_this_epoch);
  798.                   lstrcpy(szVerbLine1, szBuff);  
  799.                   ScrollWindow(hwnd, 0, -2 * cyChar, NULL, NULL);
  800.                   InvalidateRect(hwnd, NULL, FALSE);
  801.                   UpdateWindow(hwnd);
  802.                );
  803.  
  804.         /* If no_correct_flag is TRUE here, its time to stop */
  805.  
  806.         if (no_correct_flag)
  807.         {
  808.             break; /* out of the epoch loop */
  809.         }
  810.  
  811.     } /* for (i = ...) */
  812.  
  813.     /*VERBOSE(1, DestroyWindow(hwnd));*/
  814.     return(no_correct_flag);
  815. }
  816.  
  817. /*****************************************************************************
  818.  ****                                                                     ****
  819.  **** (void) atree_print(tree,verbosity)                                  ****
  820.  ****                                                                     ****
  821.  **** LPATREE tree;                                                       ****
  822.  ****                                                                     ****
  823.  **** Synopsis:                                                           ****
  824.  ****                                                                     ****
  825.  **** Prints out a tree for diagnostic and explanation purposes, the      ****
  826.  **** verbosity levels are 0 or above.  Currently, the Windows            ****
  827.  **** implementation outputs to a file called atree.out in the current    ****
  828.  **** directory.                                                          ****
  829.  *****************************************************************************/
  830.  
  831. public void FAR PASCAL
  832. atree_print(tree,verbosity)
  833.  
  834. LPATREE tree;
  835. int verbosity;
  836.  
  837. {
  838.     /*
  839.      * This routine makes an call to the private
  840.      * print tree routine that takes an extra paramater
  841.      * controlling the indentation
  842.      */
  843.  
  844.     int hOut;           /* File Handle */
  845.  
  846.     if((hOut = _lcreat("atree.out", 0)) == -1)
  847.         {
  848.         MessageBox(NULL, "Cannot open ATREE.OUT", "atree_print", MB_OK);
  849.         return;
  850.         }
  851.  
  852.     print_tree(tree,0,verbosity, hOut);
  853.     _lclose(hOut);
  854. }
  855.  
  856.  
  857. /*****************************************************************************
  858.  ****                                                                     ****
  859.  **** void atree_free(tree)                                               ****
  860.  ****                                                                     ****
  861.  **** LPATREE tree;                                                       ****
  862.  ****                                                                     ****
  863.  **** Synopsis:                                                           ****
  864.  ****                                                                     ****
  865.  **** Frees the memory used by _tree_                                     ****
  866.  *****************************************************************************/
  867.  
  868. public void FAR PASCAL
  869. atree_free(tree)
  870.  
  871. LPATREE tree;
  872.  
  873. {
  874.  
  875.     if (!(LEFTLEAF & (tree -> leaf_flag)))
  876.         atree_free(tree -> left.child);
  877.  
  878.     if (!(RIGHTLEAF & (tree -> leaf_flag)))
  879.         atree_free(tree -> right.child);
  880.  
  881.     if (tree -> seg_flag)
  882.         GlobalFree(GlobalHandle(HIWORD(tree)));
  883.  
  884.     return;
  885. }
  886.  
  887.  
  888. /*****************************************************************************
  889.  ****                                                                     ****
  890.  **** (int) atree_load(tree,name)                                         ****
  891.  ****                                                                     ****
  892.  **** LPATREE tree;                                                       ****
  893.  **** LPSTR name;                                                         ****
  894.  ****                                                                     ****
  895.  **** Synopsis:                                                           ****
  896.  ****                                                                     ****
  897.  **** Loads a previously stored tree from disk, errors signalled with a   ****
  898.  **** -1.                                                                 ****
  899.  *****************************************************************************/
  900.  
  901. /*****************************************************************************
  902.  ****                                                                     ****
  903.  **** (int) atree_store(tree,name)                                        ****
  904.  ****                                                                     ****
  905.  **** LPATREE tree;                                                       ****
  906.  **** LPSTR name;                                                         ****
  907.  ****                                                                     ****
  908.  **** Synopsis:                                                           ****
  909.  ****                                                                     ****
  910.  **** Writes the _tree_ to disk with filename _name_. Errors are          ****
  911.  **** signalled with a -1.                                                ****
  912.  *****************************************************************************/
  913.  
  914. /*****************************************************************************
  915.  ****                                                                     ****
  916.  **** LPBIT_VEC bv_create(length)                                         ****
  917.  ****                                                                     ****
  918.  **** int length;                                                         ****
  919.  ****                                                                     ****
  920.  **** Synopsis:                                                           ****
  921.  ****                                                                     ****
  922.  **** Produces a vector of _length_ bits, each one of which has been set  ****
  923.  **** to 0                                                                ****
  924.  *****************************************************************************/
  925.  
  926. public LPBIT_VEC FAR PASCAL
  927. bv_create(length)
  928.  
  929. int length;
  930.  
  931. {
  932.     int i;
  933.     LPBIT_VEC out_vec;
  934.  
  935.     assert(length > 0);
  936.  
  937.     out_vec = (LPBIT_VEC)WinMem_Malloc(LMEM_MOVEABLE | LMEM_ZEROINIT, (unsigned)sizeof(bit_vec));
  938.     MEMCHECK(out_vec);
  939.  
  940.     out_vec -> len = length;
  941.     out_vec -> bv = WinMem_Malloc(LMEM_MOVEABLE | LMEM_ZEROINIT, (unsigned) (length + BYTE - 1) / BYTE);
  942.     MEMCHECK(out_vec -> bv);
  943.  
  944.     for (i = 0; i < (length + BYTE - 1) / BYTE; i++)
  945.     {
  946.         *((out_vec -> bv) + i) = (char) 0;
  947.     }
  948.  
  949.     return(out_vec);
  950. }
  951.  
  952. /*****************************************************************************
  953.  ****                                                                     ****
  954.  **** LPBIT_VEC bv_pack(unpacked,length)                                  ****
  955.  ****                                                                     ****
  956.  **** LPSTR unpacked;                                                     ****
  957.  **** int length;                                                         ****
  958.  ****                                                                     ****
  959.  **** This routine takes an array _arr_ of zero and one characters        ****
  960.  **** and returns a packed bit vector suitable for use with the other     ****
  961.  **** routines in this library.                                           ****
  962.  *****************************************************************************/
  963.  
  964. public LPBIT_VEC FAR PASCAL
  965. bv_pack(unpacked,length)
  966.  
  967. LPSTR unpacked;
  968. int length;
  969.  
  970. {
  971.     LPBIT_VEC out_vec;
  972.     LPSTR out_ptr;
  973.     int i;
  974.     int j;
  975.     int bitptr;
  976.  
  977.     /* Create the structure */
  978.  
  979.     out_vec = (LPBIT_VEC) WinMem_Malloc(LMEM_MOVEABLE | LMEM_ZEROINIT, sizeof(bit_vec));
  980.     MEMCHECK(out_vec);
  981.  
  982.     out_vec -> len = length;
  983.     out_vec -> bv = WinMem_Malloc(LMEM_MOVEABLE | LMEM_ZEROINIT, (unsigned) (length + BYTE - 1) / BYTE);
  984.     MEMCHECK(out_vec -> bv);
  985.  
  986.     /* Pack the vector */
  987.  
  988.     out_ptr = out_vec -> bv;
  989.  
  990.     bitptr = 0;
  991.     for (i = 0; i < (length + BYTE - 1) / BYTE; i++)
  992.     {
  993.         *out_ptr = 0;
  994.  
  995.         for (j = 0; j < BYTE; j++)
  996.         {
  997.             if (bitptr < length)
  998.             {
  999.                *out_ptr |= (unpacked[bitptr] << j);
  1000.                bitptr++;
  1001.             }
  1002.             else
  1003.             {
  1004.                 break;
  1005.             }
  1006.         }
  1007.         out_ptr++;
  1008.     }
  1009.  
  1010.     /* Return the vector */
  1011.  
  1012.     return(out_vec);
  1013. }
  1014.  
  1015. /*****************************************************************************
  1016.  ****                                                                     ****
  1017.  **** int bv_diff(v1,v2)                                                  ****
  1018.  ****                                                                     ****
  1019.  **** LPBIT_VEC v1;                                                       ****
  1020.  **** LPBIT_VEC v2;                                                       ****
  1021.  ****                                                                     ****
  1022.  **** This function returns the number of bits that are unequal in the    ****
  1023.  **** two vectors. They must be the same number of bits in each vector    ****
  1024.  *****************************************************************************/
  1025.  
  1026. public int FAR PASCAL
  1027. bv_diff(v1,v2)
  1028.  
  1029. LPBIT_VEC v1;
  1030. LPBIT_VEC v2;
  1031. {
  1032.     int diff = 0;
  1033.     int i;
  1034.  
  1035.     assert (v1 -> len == v2 -> len);
  1036.     for (i = 0; i < v1 -> len; i++)
  1037.     {
  1038.         if (bv_extract(i,v1) != bv_extract(i,v2))
  1039.         {
  1040.             diff++;
  1041.         }
  1042.     }
  1043.  
  1044.     return(diff);
  1045. }
  1046.  
  1047. /*****************************************************************************
  1048.  ****                                                                     ****
  1049.  **** LPBIT_VEC bv_concat(n,vectors)                                      ****
  1050.  ****                                                                     ****
  1051.  **** int n;                                                              ****
  1052.  **** LPBIT_VEC *vectors;                                                 ****
  1053.  ****                                                                     ****
  1054.  **** Synopsis:                                                           ****
  1055.  ****                                                                     ****
  1056.  **** Returns the bit vector which is the string concatenation of each    ****
  1057.  **** bit vector in _vector_; _n_ is the number of elements in _vector_.  **** 
  1058.  *****************************************************************************/
  1059.  
  1060. public LPBIT_VEC FAR PASCAL
  1061. bv_concat(n,vector)
  1062.  
  1063. int n;
  1064. LPBIT_VEC FAR *vector;
  1065.  
  1066. {
  1067.     int size;
  1068.     LPBIT_VEC out_vec;
  1069.     LPSTR str;
  1070.     int i;
  1071.     int j;
  1072.     int count;
  1073.  
  1074.     /* Work out how big the new vector will be */
  1075.  
  1076.     size = 0;
  1077.     for (i = 0; i < n; i++)
  1078.     {
  1079.         size += vector[i] -> len;
  1080.     }
  1081.  
  1082.     /* Unpack the input vectors */
  1083.  
  1084.     str = WinMem_Malloc(LMEM_MOVEABLE | LMEM_ZEROINIT, (unsigned) size);
  1085.     MEMCHECK(str);
  1086.  
  1087.     count = 0;
  1088.     for (i = 0; i < n; i++)
  1089.     {
  1090.         for (j = 0; j < vector[i] -> len; j++)
  1091.         {
  1092.             str[count] = bv_extract(j,vector[i]);
  1093.             count++;
  1094.         }
  1095.     }
  1096.  
  1097.     out_vec = bv_pack(str,size);
  1098.  
  1099.     WinMem_Free(str);
  1100.  
  1101.     return(out_vec);
  1102. }
  1103.  
  1104.  
  1105. /*****************************************************************************
  1106.  ****                                                                     ****
  1107.  **** LPBIT_VEC bv_copy(vector)                                           ****
  1108.  ****                                                                     ****
  1109.  **** LPBIT_VEC vector;                                                   ****
  1110.  ****                                                                     ****
  1111.  **** Synopsis:                                                           ****
  1112.  ****                                                                     ****
  1113.  **** Returns a copy of the bit vector _vector_.                          ****
  1114.  *****************************************************************************/
  1115.  
  1116. public LPBIT_VEC FAR PASCAL
  1117. bv_copy(vector)
  1118.  
  1119. LPBIT_VEC vector;
  1120. {
  1121.     LPBIT_VEC out_vec;
  1122.     int i;
  1123.  
  1124.     /* Work out how big the new vector will be */
  1125.  
  1126.     out_vec = (LPBIT_VEC) WinMem_Malloc(LMEM_MOVEABLE | LMEM_ZEROINIT, sizeof(bit_vec));
  1127.     MEMCHECK(out_vec);
  1128.  
  1129.     out_vec -> len = vector -> len;
  1130.     out_vec -> bv = WinMem_Malloc(LMEM_MOVEABLE | LMEM_ZEROINIT, (unsigned) (vector -> len + BYTE - 1) / BYTE);
  1131.     MEMCHECK(out_vec -> bv);
  1132.  
  1133.     for (i = 0; i < (vector -> len + BYTE - 1) / BYTE; i++)
  1134.     {
  1135.         out_vec -> bv[i] = vector -> bv[i];
  1136.     }
  1137.  
  1138.     return(out_vec);
  1139. }
  1140.  
  1141. /*****************************************************************************
  1142.  ****                                                                     ****
  1143.  **** void bv_set(n,vec,bit)                                              ****
  1144.  ****                                                                     ****
  1145.  **** int n;                                                              ****
  1146.  **** LPBIT_VEC vec;                                                      ****
  1147.  **** BOOL bit;                                                           ****
  1148.  ****                                                                     ****
  1149.  **** Synopsis:                                                           ****
  1150.  ****                                                                     ****
  1151.  **** Sets bit _n_ in _vec_ to have the value in _bit_.                   ****
  1152.  *****************************************************************************/
  1153.  
  1154. public void FAR PASCAL
  1155. bv_set(n,vec,bit)
  1156.  
  1157. int n;
  1158. LPBIT_VEC vec;
  1159. BOOL bit;
  1160.  
  1161. {
  1162.     char mask;
  1163.     LPSTR b;
  1164.     assert(n < vec -> len);
  1165.  
  1166.     mask = 0x1;
  1167.     b = (vec -> bv) + ((int) (n / BYTE));
  1168.  
  1169.     if (bit)
  1170.     {
  1171.         *b |= (mask << (n % BYTE));
  1172.     }
  1173.     else
  1174.     {
  1175.         *b &= ~(mask << (n % BYTE));
  1176.     }
  1177. }
  1178.  
  1179. /*****************************************************************************
  1180.  ****                                                                     ****
  1181.  **** BOOL bv_extract(n,vec)                                              ****
  1182.  ****                                                                     ****
  1183.  **** int n;                                                              ****
  1184.  **** LPBIT_VEC vec;                                                      ****
  1185.  ****                                                                     ****
  1186.  **** Synopsis:                                                           ****
  1187.  ****                                                                     ****
  1188.  **** Returns the _n_th bit of _vec_.                                     ****
  1189.  *****************************************************************************/
  1190.  
  1191. public BOOL FAR PASCAL
  1192. bv_extract(n,vec)
  1193.  
  1194. int n;
  1195. LPBIT_VEC vec;
  1196.  
  1197. {
  1198.     register int mask = 0x1;
  1199.  
  1200.     assert(n < vec -> len);
  1201.     return(((*((vec -> bv) + ((int) (n / BYTE)))) & (mask << (n % BYTE))) != 0);
  1202. }
  1203.  
  1204. /*****************************************************************************
  1205.  ****                                                                     ****
  1206.  **** void bv_print(stream, vector)                                       ****
  1207.  ****                                                                     ****
  1208.  **** FILE *vector;                                                       ****
  1209.  **** LPBIT_VEC vector;                                                   ****
  1210.  ****                                                                     ****
  1211.  **** Synopsis:                                                           ****
  1212.  ****                                                                     ****
  1213.  **** Prints out _vector_ in binary, MSB is the rightmost.                ****
  1214.  *****************************************************************************/
  1215.  
  1216. public void FAR PASCAL
  1217. bv_print(stream, vector)
  1218.  
  1219. FILE *stream;
  1220. LPBIT_VEC vector;
  1221.  
  1222. {
  1223.     LPSTR ptr; /* Points to the current char */
  1224.     char mask;
  1225.     int bits; /* Counts the number of bits output */
  1226.     int  i;
  1227.  
  1228.     bits = 0;
  1229.     for (ptr = (vector -> bv);
  1230.          (ptr != (vector -> bv) + (int) ((vector -> len / BYTE) + 1)) &&
  1231.          (bits < vector -> len); ptr++)
  1232.  
  1233.     {
  1234.         mask = 0x1;
  1235.         for (i = 0; i < BYTE; i++)
  1236.         {
  1237.             if ((*ptr & mask) != 0)
  1238.             {
  1239.                 (void) fprintf(stream, "1");
  1240.             }
  1241.             else
  1242.             {
  1243.                 (void) fprintf(stream, "0");
  1244.             }
  1245.             bits++;
  1246.             if (bits == vector -> len)
  1247.             {
  1248.                 break;
  1249.             }
  1250.             mask <<= 1;
  1251.         }
  1252.     }
  1253. }
  1254.  
  1255. /*****************************************************************************
  1256.  ****                                                                     ****
  1257.  **** void bv_free(vector)                                                ****
  1258.  ****                                                                     ****
  1259.  **** LPBIT_VEC vector;                                                   ****
  1260.  ****                                                                     ****
  1261.  **** Synopsis:                                                           ****
  1262.  ****                                                                     ****
  1263.  **** Frees the memory used by _vector_                                   ****
  1264.  *****************************************************************************/
  1265.  
  1266. public void FAR PASCAL
  1267. bv_free(vector)
  1268.  
  1269. LPBIT_VEC vector;
  1270.  
  1271. {
  1272.     WinMem_Free(vector -> bv);
  1273.     WinMem_Free((LPSTR) vector);
  1274. }
  1275.  
  1276. /*****************************************************************************
  1277.  ****                                                                     ****
  1278.  **** BOOL bv_equal(v1,v2)                                                ****
  1279.  ****                                                                     ****
  1280.  **** LPBIT_VEC v1;                                                       ****
  1281.  **** LPBIT_VEC v2;                                                       ****
  1282.  ****                                                                     ****
  1283.  **** Synopsis:                                                           ****
  1284.  ****                                                                     ****
  1285.  **** Returns TRUE if each bit in v1 and v2 have the same value in the    ****
  1286.  **** same position. It returns FALSE otherwise.                          ****
  1287.  *****************************************************************************/
  1288.  
  1289. public BOOL FAR PASCAL
  1290. bv_equal(v1,v2)
  1291.  
  1292. LPBIT_VEC v1;
  1293. LPBIT_VEC v2;
  1294.  
  1295. {
  1296.     bool eq;
  1297.     int i;
  1298.  
  1299.     eq = TRUE;
  1300.  
  1301.     if (v1 -> len != v2 -> len)
  1302.     {
  1303.         eq = FALSE;
  1304.     }
  1305.     else
  1306.     {
  1307.         for (i = 0; i < (v1 -> len + BYTE - 1) / BYTE; i++)
  1308.         {
  1309.             if (v1 -> bv[i] != v2 -> bv[i])
  1310.             {
  1311.                 eq = FALSE;
  1312.                 break;
  1313.             }
  1314.         }
  1315.     }
  1316.  
  1317.     return(eq);
  1318. }
  1319.  
  1320. /*****************************************************************************
  1321.  ****                                                                     ****
  1322.  **** void FAR PASCAL Windows_Interrupt(cElapsed)                         ****
  1323.  ****                                                                     ****
  1324.  **** DWORD cElapsed                                                      ****
  1325.  ****                                                                     ****
  1326.  **** Synopsis:                                                           ****
  1327.  ****                                                                     ****
  1328.  **** Allows Windows to access other applications that may be running     ****
  1329.  **** A call to PeekMessage accomplishes this, and we process all calling ****
  1330.  **** window messages. Will only call PeekMessage if _cElapsed_ time      ****
  1331.  **** has passed since the last call to Windows_Interrupt.                ****
  1332.  ****                                                                     ****
  1333.  *****************************************************************************/
  1334.  
  1335. public void FAR PASCAL
  1336. Windows_Interrupt(cElapsed)
  1337.  
  1338. DWORD cElapsed;
  1339.  
  1340. {
  1341.     static  cTick = 0;      /* number of ticks since first called */
  1342.     MSG     msg;            /* Windows message structure */
  1343.  
  1344.     if ((GetTickCount() - cTick) > cElapsed)
  1345.         {
  1346.         if (PeekMessage(&msg, NULL, 0, 0, PM_REMOVE))
  1347.             {
  1348.             TranslateMessage(&msg);
  1349.             DispatchMessage(&msg);
  1350.             }
  1351.         cTick = GetTickCount();
  1352.         }
  1353. }
  1354.  
  1355. /*****************************************************************************
  1356.  ****                                                                     ****
  1357.  **** LPSTR FAR PASCAL  WinMem_Malloc(wFlags, wBytes)                     ****
  1358.  ****                                                                     ****
  1359.  **** WORD wFlags                                                         ****
  1360.  **** WORD wBytes                                                         ****
  1361.  ****                                                                     ****
  1362.  **** Synopsis:                                                           ****
  1363.  ****                                                                     ****
  1364.  **** Allocates _wBytes_ bytes of memory in a dynamically allocated       ****
  1365.  **** segment. _wBytes_ cannot be greater than SEGLENGTH. wFlags can be   ****
  1366.  **** any of the local memory allocation flags defined in the Windows     ****
  1367.  **** Programmer's Reference, usually LMEM_MOVEABLE.                      ****
  1368.  **** Returns a valid pointer if successful, NULL if not.                 ****
  1369.  ****                                                                     ****
  1370.  ****                                                                     ****
  1371.  *****************************************************************************/
  1372.  
  1373. public LPSTR FAR PASCAL  WinMem_Malloc(WORD wFlags, WORD wBytes)
  1374.     {
  1375.     int offset;
  1376.     int i,j;
  1377.     BOOL found;
  1378.     HANDLE hmem;
  1379.     LPSTR lp;
  1380.     PSTR p;
  1381.     LONG lSize;
  1382.     WORD wSeg;
  1383.     static BOOL bFirst = TRUE;
  1384.  
  1385.     if (bFirst) 
  1386.         {
  1387.         bFirst = FALSE;
  1388.         WinMem_Init();
  1389.         }
  1390.  
  1391.     if ((long)wBytes > (SEGLENGTH - 16)) return(NULL);
  1392.  
  1393.     for (i = 0; i < NUMSEGS; i++)
  1394.         {
  1395.         if (seg[i] == NULL)
  1396.             {
  1397.  
  1398.             /**** Get global segment, initialize local heap ****/
  1399.  
  1400.             hmem = GlobalAlloc(GMEM_MOVEABLE, SEGLENGTH);
  1401.             if (!hmem) return(NULL);
  1402.             lp = GlobalWire(hmem);
  1403.             wSeg = HIWORD(lp);
  1404.             seg[i] = hmem;
  1405.             lSize = GlobalSize(hmem) - 16;    /*
  1406.                                                * reserve 16 bytes for local
  1407.                                                * heap initialization
  1408.                                                */
  1409.             if (lSize > (SEGLENGTH - 16)) lSize = SEGLENGTH - 16;
  1410.             if (!LocalInit(wSeg,0,lSize)) return(NULL);
  1411.             freemem[i] = (WORD) lSize;
  1412.             GlobalUnlock(hmem);   /* from LocalInit */
  1413.             GlobalUnWire(hmem);
  1414.             }
  1415.         if (freemem[i] > wBytes)
  1416.             {
  1417.             lp = GlobalWire(seg[i]);
  1418.             if (!lp) return(NULL);
  1419.             wSeg = HIWORD(lp);
  1420.  
  1421.             asm { push      ds
  1422.                   mov       ax, wSeg
  1423.                   mov       ds, ax
  1424.                 }
  1425.  
  1426.             hmem = LocalAlloc(wFlags, wBytes);
  1427.  
  1428.             asm { pop       ds
  1429.                 }
  1430.  
  1431.             GlobalUnWire(seg[i]);
  1432.  
  1433.             if (hmem)
  1434.                 {
  1435.                 j = i;
  1436.                 break;
  1437.                 }
  1438.             }
  1439.         }            
  1440.  
  1441.     if (!hmem) return(NULL);
  1442.  
  1443.     lp = GlobalWire (seg[j]);       /*
  1444.                                      * move to low memory, will be
  1445.                                      * unwired in WinMem_Free
  1446.                                      */
  1447.     if (!lp) return(NULL);
  1448.     wSeg = HIWORD(lp);
  1449.  
  1450.     asm { push  ds
  1451.           mov   ax, wSeg
  1452.           mov   ds, ax
  1453.         }
  1454.  
  1455.     i = LocalSize(hmem);
  1456.     p = LocalLock (hmem);
  1457.  
  1458.     asm { pop  ds
  1459.         }
  1460.  
  1461.     freemem[j] -= i;
  1462.  
  1463.     if (!p) return(NULL);
  1464.     else    return (LPSTR)MAKELONG (p, wSeg);
  1465.     }
  1466.  
  1467. /*****************************************************************************
  1468.  ****                                                                     ****
  1469.  **** LPSTR FAR PASCAL  WinMem_Free(lpfree)                               ****
  1470.  ****                                                                     ****
  1471.  **** LPSTR lpfree                                                        ****
  1472.  ****                                                                     ****
  1473.  **** Synopsis:                                                           ****
  1474.  ****                                                                     ****
  1475.  **** Frees the block of memory in a dynamically allocated segment        ****
  1476.  **** pointed to by _lpFree_.                                             ****
  1477.  **** Returns NULL if successful, lpfree if not                           ****
  1478.  ****                                                                     ****
  1479.  ****                                                                     ****
  1480.  *****************************************************************************/
  1481.  
  1482. public LPSTR FAR PASCAL  WinMem_Free(LPSTR lpfree)
  1483.     {
  1484.     HANDLE hmem, hseg;
  1485.     LPSTR lp;
  1486.     WORD wSeg;
  1487.     int i,j;
  1488.  
  1489.     wSeg = HIWORD(lpfree);
  1490.     hseg = GlobalHandle(wSeg);
  1491.  
  1492.     j = -1;
  1493.     for (i = 0; i < NUMSEGS; i++)
  1494.         {
  1495.         if (seg[i] == hseg)
  1496.             {
  1497.             j = i;
  1498.             break;
  1499.             }
  1500.         }
  1501.     if (j == -1) return(lpfree);
  1502.  
  1503.     lp = GlobalWire(hseg);
  1504.     if (!lp) goto FAIL;
  1505.  
  1506.     asm { push  ds
  1507.           mov   ax, wSeg
  1508.           mov   ds, ax
  1509.         }
  1510.  
  1511.     hmem = LocalHandle(LOWORD(lpfree));
  1512.     if (!hmem)
  1513.         {
  1514.         asm { pop ds
  1515.             }
  1516.         goto FAIL;
  1517.         }
  1518.     
  1519.     i = LocalSize(hmem);
  1520.         
  1521.     if (!LocalUnlock (hmem))  
  1522.         {
  1523.         hmem = LocalFree(hmem);    /*returns NULL if successful*/
  1524.         if (hmem)
  1525.             {
  1526.             asm { pop ds
  1527.                 }
  1528.             goto FAIL;
  1529.             }
  1530.         }
  1531.     else
  1532.         {
  1533.         asm { pop ds
  1534.             }
  1535.         goto FAIL;
  1536.         }
  1537.  
  1538.     asm { pop   ds
  1539.         }
  1540.  
  1541.     freemem[j] += i;
  1542.  
  1543.     GlobalUnWire(hseg);
  1544.     if ((GlobalUnWire(hseg)) && (freemem[j] == (SEGLENGTH - 16))) /* TRUE if lock count at 0 */
  1545.         {
  1546.         GlobalFree(hseg);
  1547.         seg[j] = NULL;
  1548.         freemem[j] = 0;
  1549.         }
  1550.  
  1551.     return(NULL);
  1552. FAIL:
  1553.     return(lpfree);
  1554.     }
  1555.  
  1556. /*****************************************************************************
  1557.  *****************************************************************************
  1558.  ****                                                                     ****
  1559.  ****                        Private Routines                             ****
  1560.  ****                                                                     ****
  1561.  *****************************************************************************
  1562.  *****************************************************************************/
  1563.  
  1564. /*
  1565.  * void FAR PASCAL WinMem_Init()
  1566.  *
  1567.  * internal routine to initialize memory manager
  1568.  * called automatically as needed
  1569.  */
  1570.  
  1571. private void NEAR PASCAL WinMem_Init()
  1572.     {
  1573.     int i;
  1574.  
  1575.     for (i = 0; i < NUMSEGS; i++)
  1576.         {
  1577.         seg[i] = NULL;
  1578.         freemem[i] = 0;
  1579.         }
  1580.     }
  1581.  
  1582.  
  1583. /*
  1584.  * This routine recursively creates a random tree in the previously allocated
  1585.  * space starting at _tree_. It returns a pointer giving the next available
  1586.  * space for other calls.
  1587.  */
  1588.  
  1589. private LPATREE NEAR PASCAL
  1590. build_tree(connection,complemented,start,end,tree)
  1591.  
  1592. LPINT connection;
  1593. char far *complemented;
  1594. int start;
  1595. int end;
  1596. LPATREE tree;
  1597.  
  1598. {
  1599.     int mid;
  1600.     LPATREE next_node;
  1601.     LPATREE right_descendant;
  1602.  
  1603.     /* Allocate this node */
  1604.  
  1605.     tree -> function = RANDOM(4);
  1606.     tree -> sig_left = UNEVALUATED;
  1607.     tree -> sig_right = UNEVALUATED;
  1608.     if (!LOWORD(tree))  /* this node starts a segment */
  1609.         tree -> seg_flag = TRUE;
  1610.     else
  1611.         tree -> seg_flag = FALSE;
  1612.  
  1613.     switch (tree -> function)
  1614.     {
  1615.         case AND:
  1616.             tree -> cnt_10 = BELOWMID;
  1617.             tree -> cnt_01 = BELOWMID;
  1618.             break;
  1619.  
  1620.         case RIGHT:
  1621.             tree -> cnt_10 = BELOWMID;
  1622.             tree -> cnt_01 = ABOVEMID;
  1623.             break;
  1624.  
  1625.         case LEFT:
  1626.             tree -> cnt_10 = ABOVEMID;
  1627.             tree -> cnt_01 = BELOWMID;
  1628.             break;
  1629.  
  1630.         case OR:
  1631.             tree -> cnt_10 = ABOVEMID;
  1632.             tree -> cnt_01 = ABOVEMID;
  1633.             break;
  1634.     }
  1635.  
  1636.     /* Are we at a leaf ?? */
  1637.  
  1638.     if (end - start < 3)
  1639.     {
  1640.         /* This is a leaf */
  1641.  
  1642.         if (end - start == 1)
  1643.         {
  1644.             tree -> /*left*/  leaf_flag = LEFTLEAF;
  1645.             tree -> /*right*/ leaf_flag |= RIGHTLEAF;
  1646.  
  1647.             tree -> /*left*/ cmp_flag = (LEFTLEAF & complemented[start]);
  1648.             tree -> left.leaf = connection[start];
  1649.             tree -> /*right*/ cmp_flag |= (RIGHTLEAF & complemented[end]);
  1650.             tree -> right.leaf = connection[end];
  1651.  
  1652.             next_node = tree + 1;
  1653.  
  1654.         }
  1655.         else
  1656.         {
  1657.             assert(end - start == 2);
  1658.  
  1659.             tree -> /*left*/  leaf_flag = LEFTLEAF;
  1660.             tree -> /*right*/ leaf_flag &= ~(RIGHTLEAF);
  1661.             tree -> /*left*/ cmp_flag = (LEFTLEAF & complemented[start]);
  1662.             tree -> left.leaf = connection[start];
  1663.  
  1664.             tree -> right.child = tree + 1;
  1665.  
  1666.             /* segment boundary check */
  1667.  
  1668.             if (!LOWORD(tree -> right.child))     /* crossed segment bound */
  1669.                 {
  1670.                 DWORD nodes = end - start;
  1671.  
  1672.                 if (nodes >= (SEGLENGTH / sizeof(atree)))
  1673.                     tree -> right.child = (LPATREE) GlobalWire(GlobalAlloc(
  1674.                                           GMEM_MOVEABLE, SEGLENGTH));
  1675.                 else
  1676.  
  1677.                     tree -> right.child = (LPATREE) GlobalWire(GlobalAlloc(
  1678.                                           GMEM_MOVEABLE, nodes * sizeof(atree)));
  1679.                 MEMCHECK(tree -> right.child);
  1680.                 }
  1681.  
  1682.             next_node = build_tree(connection,complemented,start+1,end,tree -> right.child);
  1683.  
  1684.         }
  1685.     }
  1686.     else
  1687.     {
  1688.         /* This is a not a leaf (ie, a node) */
  1689.  
  1690.         tree -> leaf_flag = FALSE;
  1691.         tree -> cmp_flag = FALSE;
  1692.  
  1693.         /* Create left descendants */
  1694.  
  1695.         mid = start + ((end - start)/2);
  1696.         tree -> left.child = tree + 1;
  1697.  
  1698.         /* segment boundary check */
  1699.  
  1700.         if (!LOWORD(tree -> left.child))     /* crossed segment bound */
  1701.             {
  1702.             DWORD nodes = mid - start;
  1703.  
  1704.             if (nodes >= (SEGLENGTH / sizeof(atree)))
  1705.                 tree -> left.child = (LPATREE) GlobalWire(GlobalAlloc(
  1706.                                      GMEM_MOVEABLE,SEGLENGTH));
  1707.             else
  1708.                 tree -> left.child = (LPATREE) GlobalWire(GlobalAlloc(
  1709.                                      GMEM_MOVEABLE,nodes * sizeof(atree)));
  1710.  
  1711.             MEMCHECK(tree -> left.child);
  1712.             }
  1713.  
  1714.         right_descendant = build_tree(connection,complemented,start,mid,tree -> left.child);
  1715.  
  1716.         /* Create right descendants and return next available node */
  1717.  
  1718.         tree -> right.child = right_descendant;
  1719.  
  1720.         /* segment boundary check */
  1721.  
  1722.         if (!LOWORD(tree -> right.child))     /* crossed segment bound */
  1723.             {
  1724.             DWORD nodes = end - mid;
  1725.  
  1726.             if (nodes >= (SEGLENGTH / sizeof(atree)))
  1727.                 tree -> right.child = (LPATREE) GlobalWire(GlobalAlloc(
  1728.                                       GMEM_MOVEABLE,SEGLENGTH));
  1729.             else
  1730.                 tree -> right.child = (LPATREE) GlobalWire(GlobalAlloc(
  1731.                                       GMEM_MOVEABLE, nodes * sizeof(atree)));
  1732.  
  1733.             MEMCHECK(tree -> right.child);
  1734.             }
  1735.  
  1736.         next_node = build_tree(connection,complemented,mid+1,end,right_descendant);
  1737.     }
  1738.  
  1739.     return(next_node);
  1740. }
  1741.  
  1742. /*
  1743.  * print_tree routine prints out an atree to the
  1744.  * file pointed to by _fp_
  1745.  */
  1746.  
  1747. private void NEAR PASCAL
  1748. print_tree(tree,indent,verbosity,hOut)
  1749.  
  1750. LPATREE tree;
  1751. int indent;
  1752. int verbosity;
  1753. int hOut;
  1754.  
  1755. {
  1756.     int i;
  1757.     char szBuffer[80];
  1758.  
  1759.     if (RIGHTLEAF & (tree -> leaf_flag))
  1760.     {
  1761.         for (i = 0; i < indent + 3; i++)
  1762.         {
  1763.             Printf(" ",0);
  1764.             _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer));
  1765.         }
  1766.         if (RIGHTLEAF & (tree -> cmp_flag))
  1767.         {
  1768.             Printf("Leaf : !%d ",tree -> right.leaf);
  1769.             _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer));
  1770.         }
  1771.         else
  1772.         {
  1773.             Printf("Leaf : %d ",tree -> right.leaf);
  1774.             _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer));
  1775.         }
  1776.         VERBOSE(1,Printf(",",0);
  1777.                   _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer));
  1778.                   PRINTBOOL(tree -> sig_right);
  1779.                   _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer)));
  1780.  
  1781.         Printf("\r\n",0);
  1782.         _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer));
  1783.     }
  1784.     else
  1785.     {
  1786.         print_tree(tree -> right.child,indent + 3,verbosity,hOut);
  1787.     }
  1788.  
  1789.     for (i = 0; i < indent; i++)
  1790.     {
  1791.         Printf(" ",0);
  1792.         _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer));
  1793.     }
  1794.  
  1795.     switch (tree -> function)
  1796.     {
  1797.         case AND:
  1798.             Printf("AND ",0);
  1799.             _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer));
  1800.             break;
  1801.  
  1802.         case RIGHT:
  1803.             Printf("RIGHT ",0);
  1804.             _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer));
  1805.             break;
  1806.  
  1807.         case LEFT:
  1808.             Printf("LEFT ",0);
  1809.             _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer));
  1810.             break;
  1811.  
  1812.         case OR:
  1813.             Printf("OR ",0);
  1814.             _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer));
  1815.             break;
  1816.     }
  1817.  
  1818.     VERBOSE(1, Printf("rsp = ",0);
  1819.               _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer));
  1820.               Printf(",r=",0);
  1821.               _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer));
  1822.               PRINTBOOL(tree -> sig_right);
  1823.               _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer));
  1824.               Printf(",l=",0);
  1825.               _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer));
  1826.               PRINTBOOL(tree -> sig_left);
  1827.               _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer)));
  1828.  
  1829.     Printf("\r\n",0);
  1830.     _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer));
  1831.  
  1832.     if (LEFTLEAF & (tree -> leaf_flag))
  1833.     {
  1834.         for (i = 0; i < indent + 3; i++)
  1835.         {
  1836.             Printf(" ",0);
  1837.             _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer));
  1838.         }
  1839.         if (LEFTLEAF & (tree -> cmp_flag))
  1840.         {
  1841.             Printf("Leaf : !%d ",tree -> left.leaf);
  1842.             _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer));
  1843.         }
  1844.         else
  1845.         {
  1846.             Printf("Leaf : %d ",tree -> left.leaf);
  1847.             _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer));
  1848.         }
  1849.  
  1850.         VERBOSE(1,Printf(",",0);
  1851.         _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer));
  1852.         PRINTBOOL(tree -> sig_left);
  1853.         _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer)));
  1854.  
  1855.         Printf("\r\n",0);
  1856.         _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer));
  1857.     }
  1858.     else
  1859.     {
  1860.         print_tree(tree -> left.child,indent + 3,verbosity, hOut);
  1861.     }
  1862. }
  1863.  
  1864. /*
  1865.  * bool train(tree,vec,result)
  1866.  *
  1867.  * LPATREE tree;
  1868.  * LPBITVEC vec;
  1869.  * bool result;
  1870.  *
  1871.  * This routine is actually responsible for the training of a tree for a
  1872.  * single input vector and result. If the tree gets the correct result
  1873.  * before the adaptation step occurs, the routine returns TRUE, otherwise,
  1874.  * false.
  1875.  */
  1876.  
  1877. private bool NEAR PASCAL
  1878. train(tree,vec,result)
  1879.  
  1880. LPATREE tree;
  1881. LPBIT_VEC vec;
  1882. bool result;
  1883.  
  1884. {
  1885.     bool correct;
  1886.  
  1887.     /* What does the tree currently think ?*/
  1888.  
  1889.     correct = (bool)atree_eval(tree,vec) == result;
  1890.  
  1891.     /* Adapt the tree */
  1892.  
  1893.     adapt(tree,vec,result);
  1894.  
  1895.     /* Did the tree get it right ? */
  1896.  
  1897.     correct = (bool)atree_eval(tree,vec) == result;
  1898.  
  1899.     /* If not, try again ! */
  1900.  
  1901.     if (!correct)
  1902.     {
  1903.         adapt(tree,vec,result);
  1904.     }
  1905.  
  1906.     return(correct);
  1907. }
  1908.  
  1909. /*
  1910.  * adapt(tree,vec,result)
  1911.  *
  1912.  * LPATREE tree;
  1913.  * LPBIT_VEC vec;
  1914.  * bool result;
  1915.  *
  1916.  */
  1917.  
  1918. private void NEAR PASCAL
  1919. adapt(tree,vec,result)
  1920.  
  1921. LPATREE tree;
  1922. LPBIT_VEC vec;
  1923. bool result;
  1924.  
  1925. {
  1926.  
  1927. /*
  1928.  * INCR and DECR implement bounded counters, remembering that TRUE == 1,
  1929.  * how much should be added to t when t == MAXSET ?
  1930.  */
  1931.  
  1932. #define INCR(t) t += (t != MAXSET)
  1933. #define DECR(t) t -= (t != MINSET)
  1934.  
  1935.     /* If the left child is unevaluated, evaluate it */
  1936.  
  1937.     if (tree -> sig_left == UNEVALUATED)
  1938.     {
  1939.       LEFTEVAL;
  1940.     }
  1941.  
  1942.     /* If the right child is unevaluated, evaluate it */
  1943.  
  1944.     if (tree -> sig_right == UNEVALUATED)
  1945.     {
  1946.       RIGHTEVAL;
  1947.     }
  1948.  
  1949.     /* Update the counters if needed */
  1950.  
  1951.     if (tree -> sig_left != tree -> sig_right)
  1952.     {
  1953.         if (tree -> sig_left)
  1954.         {
  1955.             if (tree -> sig_left == result)
  1956.             {
  1957.                 INCR(tree -> cnt_10);
  1958.             }
  1959.             else
  1960.             {
  1961.                 DECR(tree -> cnt_10);
  1962.             }
  1963.  
  1964.         }
  1965.         else
  1966.         {
  1967.             assert(tree -> sig_right);
  1968.  
  1969.             if (tree -> sig_right == result)
  1970.             {
  1971.                 INCR(tree -> cnt_01);
  1972.             }
  1973.             else
  1974.             {
  1975.                 DECR(tree -> cnt_01);
  1976.             }
  1977.         }
  1978.  
  1979.         /* has the node function changed */
  1980.  
  1981.         tree -> function = node_function(tree);
  1982.     }
  1983.  
  1984.     /* Assign responsibility to the left child */
  1985.  
  1986.     if (!(LEFTLEAF & (tree -> leaf_flag)))
  1987.     {
  1988.         if (tree -> sig_right != result)
  1989.         {
  1990.             adapt(tree -> left.child,vec,result);
  1991.         }
  1992.         else if ((tree -> function == LEFT) || (tree -> function == RIGHT))
  1993.         {
  1994.             adapt(tree -> left.child,vec,result);
  1995.         }
  1996.         else
  1997.         {
  1998.             if (tree -> sig_right)
  1999.             {
  2000.                 if (tree -> cnt_01 < ABOVEMID)
  2001.                 {
  2002.                     adapt(tree -> left.child,vec,result);
  2003.                 }
  2004.             }
  2005.             else
  2006.             {
  2007.                 if (tree -> cnt_10 >= ABOVEMID)
  2008.                 {
  2009.                     adapt(tree -> left.child,vec,result);
  2010.                 }
  2011.             }
  2012.         }
  2013.     }
  2014.  
  2015.     /* Assign responsibility to the right child */
  2016.  
  2017.     if (!(RIGHTLEAF & (tree -> leaf_flag)))
  2018.     {
  2019.         if (tree -> sig_left != result)
  2020.         {
  2021.             adapt(tree -> right.child,vec,result);
  2022.         }
  2023.         else if ((tree -> function == LEFT) || (tree -> function == RIGHT))
  2024.         {
  2025.             adapt(tree -> right.child,vec,result);
  2026.         }
  2027.         else
  2028.         {
  2029.             if (tree -> sig_left)
  2030.             {
  2031.                 if (tree -> cnt_10 < ABOVEMID)
  2032.                 {
  2033.                     adapt(tree -> right.child,vec,result);
  2034.                 }
  2035.             }
  2036.             else
  2037.             {
  2038.                 if (tree -> cnt_01 >= ABOVEMID)
  2039.                 {
  2040.                     adapt(tree -> right.child,vec,result);
  2041.                 }
  2042.             }
  2043.         }
  2044.     }
  2045. }
  2046.  
  2047. private char NEAR PASCAL
  2048. node_function(tree)
  2049.  
  2050. LPATREE tree;
  2051. {
  2052.     char result;
  2053.  
  2054.     if (tree -> cnt_10 >= ABOVEMID)
  2055.     {
  2056.         if (tree -> cnt_01 >= ABOVEMID)
  2057.         {
  2058.             result = OR;
  2059.         }
  2060.         else
  2061.         {
  2062.             result = LEFT;
  2063.         }
  2064.     }
  2065.     else
  2066.     {
  2067.         if (tree -> cnt_01 >= ABOVEMID)
  2068.         {
  2069.             result = RIGHT;
  2070.         }
  2071.         else
  2072.         {
  2073.             result = AND;
  2074.         }
  2075.     }
  2076.  
  2077.     return(result);
  2078. }
  2079.  
  2080.  
  2081. #pragma warn -rvl
  2082.  
  2083. error(s)
  2084.  
  2085. char *s;
  2086.  
  2087. {
  2088.     char szBuffer[80];
  2089.  
  2090.     wsprintf(szBuffer,"Error: %s ", s);
  2091.     MessageBox(NULL,szBuffer,"ERROR",MB_OK);
  2092.     exit(0);
  2093. }
  2094.  
  2095. #pragma warn .rvl
  2096.